package com.example.learndemo.dataAlgorithm;

import com.example.learndemo.TestCommon;

public class ArraySort {
	static int sum = 0;

	/**
	 * 插入排序
	 *
	 * @param data
	 */
	public static void insertSort(int[] data) {
		long start = System.currentTimeMillis();
		insertSortByIncr(data, 1);
		System.out.println("数组长度=" + data.length + "  insertSort执行时长==>" + (System.currentTimeMillis() - start));
	}

	/**
	 * 希尔排序 插入排序的升级版，
	 *
	 * @param data
	 */
	public static void shellSort(int[] data) {
		long start = System.currentTimeMillis();
		for (int incr = data.length >> 1; incr > 0; incr = incr >> 1) {// incr=增量 增量每次除2 logn
			insertSortByIncr(data, incr);
		}
		System.out.println("数组长度=" + data.length + "  shellSort执行时长==>" + (System.currentTimeMillis() - start));

	}

	/**
	 * 插入排序抽取方法，增量为1
	 *
	 * @param data 待排序数组
	 * @param incr 增量，按数组下标变量每次下标 增或者减 incr
	 */
	private static void insertSortByIncr(int[] data, int incr) {
		int length = data.length;
		for (int j = incr; j < length; j += incr) {// n
			int temp = data[j];
			for (int k = j - incr; k >= 0; k -= incr) {// 1+2+....n-1
				sum++;
				if (temp < data[k]) {
					data[k + incr] = data[k];
					data[k] = temp;
				} else {
					break;
				}
			}
		}
	}

	/**
	 * 快速排序：效率比归并排序要高，但是不是稳定排序
	 * @param left
	 * @param right
	 * @param data
	 */
	private static void fastSort(int left, int right, int[] data) {
		if (left >= right) {
			return;
		}
		int a = data[left];
		int oldLeft = left;
		int oldRight = right;
		while (left < right) {
			while (a < data[right] && left < right) {
				right--;
			}
			if (left < right) {
				data[left] = data[left] ^ data[right];
				data[right] = data[left] ^ data[right];
				data[left] = data[left] ^ data[right];
				left++;
			}
			while (a > data[left] && left < right) {
				left++;
			}
			if (left < right) {
				data[left] = data[left] ^ data[right];
				data[right] = data[left] ^ data[right];
				data[left] = data[left] ^ data[right];
				right--;
			}
		}
		fastSort(oldLeft, left - 1, data);
		fastSort(left + 1, oldRight, data);
	}


	// 归并排序
	public static void mergeSort(int[] data) {
		long start = System.currentTimeMillis();
		mergeSortRecursion(0, data.length - 1, data);
		System.out.println("数组长度=" + data.length + "   mergeSort执行时长==>" + (System.currentTimeMillis() - start));

	}

	public static void fastSort(int[] data) {
		long start = System.currentTimeMillis();
		fastSort(0, data.length - 1, data);
		System.out.println("数组长度=" + data.length + "   fastSort执行时长==>" + (System.currentTimeMillis() - start));

	}

	private static void mergeSortRecursion(int left, int right, int[] data) {
		if (left >= right) {
			return;
		}
		int mid = (left + right) >> 1;
		mergeSortRecursion(left, mid, data);
		mergeSortRecursion(mid + 1, right, data);
		// 拆完了，开始组装
		int[] temp = new int[right - left + 1];// 创建一个临时数组，长度整好能装下左右两部分数组
		int loc = 0;
		int leftPos = left;
		int rightPos = mid + 1;
		while (leftPos <= mid && rightPos <= right) {
			sum++;
			if (data[leftPos] <= data[rightPos]) {
				temp[loc++] = data[leftPos++];
			} else {
				temp[loc++] = data[rightPos++];
			}
		}
		while (leftPos <= mid) {
			sum++;
			temp[loc++] = data[leftPos++];
		}
		while (rightPos <= right) {
			sum++;
			temp[loc++] = data[rightPos++];
		}
		// 将临时数组最开始下标对应待排序最左边位置，开始遍历按顺序复制
		System.arraycopy(temp, 0, data, left, temp.length);
	}


	public static void main(String[] args) throws Exception {
		for (int i = 0; i < 100; i++) {

			int length = 1000000;
			int[] data = TestCommon.creatArr(length);
			int[] data2 = TestCommon.copyArr(data);
			int[] data3 = TestCommon.copyArr(data);
			// System.out.println("----------------------");
			// insertSort(data);
			// TestCommon.print(data);
			// System.out.println("insertSort==>" + sum);
			// sum = 0;
			// shellSort(data2);
			// TestCommon.print(data2);
			// System.out.println("shellSort===>" + sum);
			// sum = 0;
			mergeSort(data3);
			// TestCommon.print(data3);
			System.out.println("mergeSort===>" + sum);
			fastSort(data);
			// TestCommon.print(data);
			TestCommon.equals(data, data3);
		}

	}



}
